// `include "butterfly2.v"
module fft_64 (
  input  wire        clk             , // 系统时钟
  input  wire        rst_n           , // 系统异步复位，低电平有效

  input  wire        inv             , // 模式控制，0表示FFT运算，1表示IFFT运算

  input  wire        valid_in        , // 输入数据有效指示，高电平有效

  input  wire        sop_in          , // 每组输入数据（64个数）第一个有效数据指示，高电平有效

  input  wire signed [15:0] x_re     , // 输入数据实部，二进制补码定点格式
  input  wire signed [15:0] x_im     , // 输入数据虚部，二进制补码定点格式

  output reg         valid_out       , // 输出数据有效指示，高电平有效

  output reg         sop_out         , // 每组输出数据（64个数）第一个有效数据指示，高电平有效
  
  output reg  signed [15:0] y_re     , // 输出数据实部，二进制补码定点格式
  output reg  signed [15:0] y_im       // 输出数据虚部，二进制补码定点格式
);
// https://blog.csdn.net/weixin_43623428/article/details/119281728
// https://blog.csdn.net/weixin_40640020/article/details/84310283
// input / output index
wire [5:0] index [63:0];
assign{
  index[ 0],index[ 1],index[ 2],index[ 3],index[ 4],index[ 5],index[ 6],index[ 7],index[ 8],index[ 9],
  index[10],index[11],index[12],index[13],index[14],index[15],index[16],index[17],index[18],index[19],
  index[20],index[21],index[22],index[23],index[24],index[25],index[26],index[27],index[28],index[29],
  index[30],index[31],index[32],index[33],index[34],index[35],index[36],index[37],index[38],index[39],
  index[40],index[41],index[42],index[43],index[44],index[45],index[46],index[47],index[48],index[49],
  index[50],index[51],index[52],index[53],index[54],index[55],index[56],index[57],index[58],index[59],
  index[60],index[61],index[62],index[63] 
} = {
  6'd0     ,6'd32    ,6'd16    ,6'd48    ,6'd8     ,6'd40    ,6'd24    ,6'd56    ,6'd4     ,6'd36    ,
  6'd20    ,6'd52    ,6'd12    ,6'd44    ,6'd28    ,6'd60    ,6'd2     ,6'd34    ,6'd18    ,6'd50    ,
  6'd10    ,6'd42    ,6'd26    ,6'd58    ,6'd6     ,6'd38    ,6'd22    ,6'd54    ,6'd14    ,6'd46    ,
  6'd30    ,6'd62    ,6'd1     ,6'd33    ,6'd17    ,6'd49    ,6'd9     ,6'd41    ,6'd25    ,6'd57    ,
  6'd5     ,6'd37    ,6'd21    ,6'd53    ,6'd13    ,6'd45    ,6'd29    ,6'd61    ,6'd3     ,6'd35    ,
  6'd19    ,6'd51    ,6'd11    ,6'd43    ,6'd27    ,6'd59    ,6'd7     ,6'd39    ,6'd23    ,6'd55    ,
  6'd15    ,6'd47    ,6'd31    ,6'd63    
};

// factor, multiplied by 0x2000
// 旋转因子数量 N/2=32
wire signed [15:0] factor_real [31:0];
wire signed [15:0] factor_imag [31:0];
assign{
  factor_real[ 0],factor_real[ 1],factor_real[ 2],factor_real[ 3],factor_real[ 4],factor_real[ 5],factor_real[ 6],factor_real[ 7],factor_real[ 8],factor_real[ 9],
  factor_real[10],factor_real[11],factor_real[12],factor_real[13],factor_real[14],factor_real[15],factor_real[16],factor_real[17],factor_real[18],factor_real[19],
  factor_real[20],factor_real[21],factor_real[22],factor_real[23],factor_real[24],factor_real[25],factor_real[26],factor_real[27],factor_real[28],factor_real[29],
  factor_real[30],factor_real[31]
} = {

  16'h2000       ,16'h1FD8       ,16'h1F62      ,16'h1E9F        ,16'h1D90       ,16'h1C38       ,16'h1A9B       ,16'h18BC       ,16'h16A0       ,16'h144C       ,
  16'h11C7       ,16'h0F15       ,16'h0C3E       ,16'h094A       ,16'h063E       ,16'h0322       ,16'h0000       ,16'hFCDD       ,16'hF9C1       ,16'hF6B5       ,
  16'hF3C1       ,16'hF0EA       ,16'hEE38       ,16'hEBB3       ,16'hE95F       ,16'hE743       ,16'hE564       ,16'hE3C7       ,16'hE26F       ,16'hE160       ,
  16'hE09D       ,16'hE027        
};
assign{
  factor_imag[ 0],factor_imag[ 1],factor_imag[ 2],factor_imag[ 3],factor_imag[ 4],factor_imag[ 5],factor_imag[ 6],factor_imag[ 7],factor_imag[ 8],factor_imag[ 9],
  factor_imag[10],factor_imag[11],factor_imag[12],factor_imag[13],factor_imag[14],factor_imag[15],factor_imag[16],factor_imag[17],factor_imag[18],factor_imag[19],
  factor_imag[20],factor_imag[21],factor_imag[22],factor_imag[23],factor_imag[24],factor_imag[25],factor_imag[26],factor_imag[27],factor_imag[28],factor_imag[29],
  factor_imag[30],factor_imag[31]
} = {
  16'h0000       ,16'hFCDD       ,16'hF9C1       ,16'hF6B5       ,16'hF3C1       ,16'hF0EA       ,16'hEE38       ,16'hEBB3       ,16'hE95F       ,16'hE743       ,
  16'hE564       ,16'hE3C7       ,16'hE26F       ,16'hE160       ,16'hE09D       ,16'hE027       ,16'hE000       ,16'hE027       ,16'hE09D       ,16'hE160       ,
  16'hE26F       ,16'hE3C7       ,16'hE564       ,16'hE743       ,16'hE95F       ,16'hEBB3       ,16'hEE38       ,16'hF0EA       ,16'hF3C1       ,16'hF6B5       ,
  16'hF9C1       ,16'hFCDD        
};

// generate adder
reg [5:0] counter;
wire [5:0] counter_next = {6{sop_in }} & 6'b0 
                        | {6{~sop_in}} & (counter + 1);
always @(posedge clk or negedge rst_n) begin
  if (~rst_n) begin
    counter <= 0;
  end
  else if (valid_in) begin
    counter <= counter_next;
  end
end

// store input
reg signed [15:0] mem_xm_real[63:0];
reg signed [15:0] mem_xm_imag[63:0];
reg inv_reg ;
always @(posedge clk or negedge rst_n) begin
  if (~rst_n) begin
  end
  else if (valid_in) begin
    mem_xm_real[counter_next] <= x_re;
    mem_xm_imag[counter_next] <= {16{~inv}}&x_im | {16{inv}}&(-x_im); // inv==0 -> fft   inv==1 -> ifft
    inv_reg <= inv;
  end
end

// fft input
// N=64; m=log2(N)-1=5; k=N/2-1=31
// 64个点 6级运算+1级输入
wire signed [15:0] xm_real[6:0][63:0];
wire signed [15:0] xm_imag[6:0][63:0];
wire   en_connect [223:0] ;
wire   en = counter==63;
assign {
  en_connect[ 0],en_connect[ 1],en_connect[ 2],en_connect[ 3],en_connect[ 4],en_connect[ 5],en_connect[ 6],en_connect[ 7],en_connect[ 8],en_connect[ 9],
  en_connect[10],en_connect[11],en_connect[12],en_connect[13],en_connect[14],en_connect[15],en_connect[16],en_connect[17],en_connect[18],en_connect[19],
  en_connect[20],en_connect[21],en_connect[22],en_connect[23],en_connect[24],en_connect[25],en_connect[26],en_connect[27],en_connect[28],en_connect[29],
  en_connect[30],en_connect[31] 
} = {
  en            ,en            ,en            ,en            ,en            ,en            ,en            ,en            ,en            ,en            ,
  en            ,en            ,en            ,en            ,en            ,en            ,en            ,en            ,en            ,en            ,
  en            ,en            ,en            ,en            ,en            ,en            ,en            ,en            ,en            ,en            ,
  en            ,en            
};

//input initial

genvar czw;
generate
  for (czw = 0; czw<=63; czw=czw+1) begin
    assign xm_real[0][czw] = mem_xm_real[index[czw]]; //输入地址二进制码翻转
    assign xm_imag[0][czw] = mem_xm_imag[index[czw]];
  end
endgenerate

//butter instantiaiton
genvar m, k;
generate
   //6 stage
   for(m=0; m<=5; m=m+1) begin: stage
      for (k=0; k<=31; k=k+1) begin: unit
         butterfly2 u_butter(
            .clk         (clk                                      ) ,
            .rstn        (rst_n                                    ) ,
            .en          (en_connect[m*32 + k]                     ) ,

             //input data
            .xp_real     (xm_real[ m ] [k[m:0] < (1<<m) ?
                                        (k[31:m] << (m+1)) + k[m:0] :
                                        (k[31:m] << (m+1)) + (k[m:0]-(1<<m))] ),
            .xp_imag     (xm_imag[ m ] [k[m:0] < (1<<m) ?
                                        (k[31:m] << (m+1)) + k[m:0] :
                                        (k[31:m] << (m+1)) + (k[m:0]-(1<<m))] ),
            .xq_real     (xm_real[ m ] [(k[m:0] < (1<<m) ?
                                        (k[31:m] << (m+1)) + k[m:0] :
                                        (k[31:m] << (m+1)) + (k[m:0]-(1<<m))) + (1<<m) ]),
            .xq_imag     (xm_imag[ m ] [(k[m:0] < (1<<m) ?
                                        (k[31:m] << (m+1)) + k[m:0] :
                                        (k[31:m] << (m+1)) + (k[m:0]-(1<<m))) + (1<<m) ]),

            .factor_real (factor_real[(k[m:0]<(1<<m)? k[m:0] : k[m:0]-(1<<m))<<(5-m) ]),
            .factor_imag (factor_imag[(k[m:0]<(1<<m)? k[m:0] : k[m:0]-(1<<m))<<(5-m) ]),

            //output data
            .valid       (en_connect[ (m+1)*32 + k ]                ),
            .yp_real     (xm_real[ m+1 ][k[m:0] < (1<<m) ?
                                         (k[31:m] << (m+1)) + k[m:0] :
                                         (k[31:m] << (m+1)) + (k[m:0]-(1<<m))] ),
            .yp_imag     (xm_imag[ m+1 ][k[m:0] < (1<<m) ?
                                         (k[31:m] << (m+1)) + k[m:0] :
                                         (k[31:m] << (m+1)) + (k[m:0]-(1<<m))] ),
            .yq_real     (xm_real[ m+1 ][(k[m:0] < (1<<m) ?
                                         (k[31:m] << (m+1)) + k[m:0] :
                                         (k[31:m] << (m+1)) + (k[m:0]-(1<<m))) + (1<<m) ]),
            .yq_imag     (xm_imag[ m+1 ][((k[m:0]) < (1<<m) ?
                                         (k[31:m] << (m+1)) + k[m:0] :
                                         (k[31:m] << (m+1)) + (k[m:0]-(1<<m))) + (1<<m) ])
          );
      end
   end
endgenerate

// inv_r
reg [17:0] inv_r;
always @(posedge clk or negedge rst_n) begin
  if (~rst_n) begin
    inv_r <= 0; // 默认fft
  end
  else begin
    inv_r <= {inv_r[16:0], en_connect[0]  & inv_reg
                        |  ~en_connect[0] & inv_r[0]};
  end
end

// generate out adder
wire sop_out_next = en_connect[192];
reg [5:0] counter_o;
wire [5:0] counter_next_o = {6{sop_out_next }} & 6'b0 
                          | {6{~sop_out_next}} & (counter_o + 1);

always @(posedge clk or negedge rst_n) begin
  if (~rst_n) begin
    counter_o <= 0;
    sop_out <= 0;
    valid_out <= 0;
    y_re <= 0;
    y_im <= 0;
  end
  else begin
    counter_o <= counter_next_o;
    y_re <= xm_real[6][counter_next_o];
    y_im <= {16{~inv_r[17]}}&xm_imag[6][counter_next_o] | {16{inv_r[17]}}&(-xm_imag[6][counter_next_o]); // inv==0 -> fft   inv==1 -> ifft
    if(sop_out_next) begin
      sop_out <= sop_out_next;
      valid_out <= 1;
    end
    else if (~sop_out_next && counter_o==63) begin
      sop_out <= 0;
      valid_out <= 0;
    end
    else begin
      sop_out <= 0;
      valid_out <= valid_out;
    end
  end
end
endmodule